package com.yuqingsong.algorithm.sort;

import java.util.Arrays;
import java.util.Comparator;

public class InsertSort<T> extends AbstractSort<T> {

	public InsertSort( Comparator<? super T> comp) {
		init(comp);
	}


	@Override
	public T[] sort(T[] array) {
		for (int i = 1; i < array.length; i++) {
			T current = array[i];
			int j = i - 1;
			/*
			 * 如果array[j]前一个元素大于current,将array[j]移到下一个位置
			 */
			for (; j > -1 && comp.compare(current, array[j]) < 0; j--) {
				array[j + 1] = array[j];
			}
			//将current设置到j+1位置
			array[j + 1] = current;
		}
		return array;
	}

	@Override
	public String toString() {
		return "InsertSort";
	}
	
	public static void main(String[] args) {
		Integer[] temp = null;
		temp = new Integer[] { 16, 14, 8, 7, 9, 3, 2, 4, 1 };

		Comparator<Integer> comp = new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {
				return o1 - o2;
			}
		};
		Sort<Integer> sort = new InsertSort<Integer>( comp);
		Integer[] clone = temp.clone();
		Arrays.sort(clone);
		boolean equals = Arrays.equals(clone, sort.sort(temp));
		assert equals;
		System.out.println(Arrays.toString(temp));
	}

}
